package com.origin.niuke.point;

/**
 * 丑数
 * 算法：数学 + 三指针
 *
 * @author yezh
 * @version 1.0
 * @date 2022/11/9 22:53
 */
public class NC79 {

    public int GetUglyNumber_Solution(int index) {
        int t2 = 1, t3 = 1, t5 = 1;
        int[] dp = new int[index + 2];
        dp[1] = 1;
        for (int i = 2; i <= index; i++) {
            int a = dp[t2] * 2, b = dp[t3] * 3, c = dp[t5] * 5;
            int min = Math.min(a, Math.min(b, c));
            dp[i] = min;
            // 这里不能使用 if else, a,b,c 可能会相同
            if (a == min) ++t2;
            if (b == min) ++t3;
            if (c == min) ++t5;
        }
        return dp[index];
    }

}
